The following references are cited in the specification. Disclosures of these references are incorporated herein by reference in their entirety.
List of References    W. K. Chan, J. G. Yi, and S. W. Ding, “Optimal Scheduling of Multi-cluster Tools with Constant Robot Moving Times, Part I: Two-Cluster Analysis,” IEEE Transactions on Automation Science and Engineering, vol. 8, pp. 5-16, 2011a.    W. K. Chan, J. G. Yi, S. W. Ding, and D. Z. Song, “Optimal Scheduling of Multi-cluster Tools with Constant Robot Moving Times, Part II: Tree-Like Topology Configurations,” IEEE Transactions on Automation Science and Engineering, vol. 8, pp. 17-28, 2011b.    M. Dawande, C. Sriskandarajah, and S. Sethi, “On throughput maximization in constant travel-time robotic cells”, Manufacturing and Service Operations Management, vol. 4, no. 4, 296-312, 2002.    S. W. Ding, J. G. Yi, and M. T. Zhang, “Multicluster Tools Scheduling: an Integrated Event Graph and Network Model Approach,” IEEE Transactions on Semiconductor Manufacturing, vol. 19, pp. 339-351, 2006.    I. Drobouchevitch, S. P. Sethi, and C. Sriskandarajah, “Scheduling Dual Gripper Robotic Cells: One-unit Cycles,” European Journal of Operational Research, vol. 171, pp. 598-631, 2006.    D. Jevtic, “Method and Apparatus for Managing Scheduling a Multiple Cluster Tool,” in European Patent. vol. 1,132,792(A2), 2001.    D. Jevtic and S. Venkatesh, “Method and Apparatus for Scheduling Wafer Processing within a Multiple Chamber Semiconductor Wafer Processing Tool Having a Multiple Blade Robot,” in U.S. Pat. No. 6,224,638, 2001.    J. -H. Kim, T. -E. Lee, H. -Y. Lee, and D. -B. Park, Scheduling analysis of timed-constrained dual-armed cluster tools, IEEE Transactions on Semiconductor Manufacturing, vol. 16, no. 3, 521-534, 2003.    T. -E. Lee, H. -Y. Lee, and Y. -H. Shin, Workload balancing and scheduling of a single-armed cluster tool, in Proceedings of the 5th APIEMS Conference, Gold Coast, Australia, 1-15, 2004.    T. -E. Lee and S. -H. Park, “An extended event graph with negative places and tokens for timed window constraints,” IEEE Transactions on Automation Science and Engineering, vol. 2, no. 4, 319-332, 2005.    M. -J. Lopez and S. -C. Wood, Systems of multiple cluster tools—configuration, reliability, and performance, IEEE Transactions on Semiconductor Manufacturing, vol. 16, no. 2, 170-178, 2003.    T. L. Perkinson, R. S. Gyurcsik, and P. K. MacLarty, “Single-wafer cluster tool performance: An analysis of the effects of redundant chambers and revisitations sequences on throughput,” IEEE Transactions on Semiconductor Manufacturing, vol. 9, 384-400, 1996.    T. L. Perkinson, P. K. MacLarty, R. S. Gyurcsik, and R. K. Cavin, III, “Single-wafer cluster tool performance: An analysis of throughput,” IEEE Transactions on Semiconductor Manufacturing, vol. 7, 369-373, 1994.    S. Rostami, B. Hamidzadeh, and D. Camporese, “An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints,” IEEE Transactions on Robotics and Automation, vol. 17, 609-618, 2001.    S. Venkatesh, R. Davenport, P. Foxhoven, and J. Nulman, A steady state throughput analysis of cluster tools: Dual-blade versus single-blade robots, IEEE Trans. Semi-conduct. Manuf., vol.10, pp. 418-424, 1997.    N. Q. Wu, “ Necessary and Sufficient Conditions for Deadlock-free Operation in Flexible Manufacturing System Using a Colored Petri Net Model,” IEEE Transaction on System, Man, and Cybernetics, Part C, vol. 29, pp. 192-204, 1999.    N. Q. Wu, C. B. Chu, F. Chu, and M. C. Zhou, “A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints,” IEEE Transactions on Semiconductor Manufacturing, vol. 21, pp. 224-237, 2008a.    N. Q. Wu, F. Chu, C. Chu, and M. Zhou, “Petri Net-Based Scheduling of Single-Arm Cluster Tools With Reentrant Atomic Layer Deposition Processes,” IEEE Transactions on Automation Science and Engineering, vol. 8, pp. 42-55, January 2011.    N. Q. Wu, F. Chu, C. B. Chu, and M. C. Zhou, “Petri net modeling and cycle time analysis of dual-arm cluster tools with wafer revisiting,” IEEE Transactions on Systems, Man, & Cybernetics, Part A, in press, 2012.    N. Q. Wu and M. C. Zhou, System modeling and control with resource-oriented Petri nets, CRC Press, Taylor & Francis Group, New York, October 2009.    N. Q. Wu and M. Zhou, “Analysis of wafer sojourn time in dual-arm cluster tools with residency time constraint and activity time variation,” IEEE Transactions on Semiconductor Manufacturing, vol. 23, pp. 53-64, 2010a.    N. Q. Wu and M. C. Zhou, “A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools based on steady schedule analysis,” IEEE Transactions on Automation Science and Engineering, vol. 7, no. 2, 303-315, 2010b.    N. Q. Wu and M. C. Zhou, Process vs resource-oriented Petri net modeling of automated manufacturing systems, Asian Journal of Control, vol. 12, no. 3, 267-280, 2010c.    N. Q. Wu and M. C. Zhou, “Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets,” IEEE Transactions on Automation Science and Engineering, vol. 9, no. 2, 446-454, 2012a.    N. Q. Wu and M. C. Zhou, “Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation,” IEEE Transactions on Automation Science and Engineering, vol. 9, no. 1, 203-209, 2012b.    N. Q. Wu, M. C. Zhou, and Z. W. Li, Resource-oriented Petri net for deadlock avoidance in flexible assembly systems, IEEE Transactions on System, Man, & Cybernetics, Part A, vol. 38, no. 1, 56-69, 2008b.    F. J. Yang, N. Q. Wu, Y. Qiao, and M. C. Zhou, Petri net-based optimal one-wafer cyclic scheduling of hybrid multi-cluster tools in wafer fabrication, IEEE Transactions on Semiconductor Manufacturing, vol. 27, no. 2, 192-203, 2014a.    F. J. Yang, N. Q. Wu, Y. Qiao, and M. C. Zhou, Optimal one-wafer cyclic scheduling of single-arm multi-cluster tools with two-space buffering modules, IEEE Transactions on Systems, Man, & Cybernetics: Systems, vol. 44, no. 12, 1584-1597, 2014b.    J. G. Yi, S. W. Ding, D. Z. Song, and M. T. Zhang, “Steady-State Throughput and Scheduling Analysis of Multi-Cluster Tools for Semiconductor Manufacturing: A Decomposition Approach,” IEEE Transactions on Automation Science and Engineering, vol. 5, pp. 321-336, 2008.    M. C. Zhou and K. Venkatesh, Modeling, simulation and control of flexible manufacturing systems: Petri net approach, World Scientific, Singapore, 1998.    Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, Petri net-based optimal one-wafer scheduling of single-arm multi-cluster tools in semiconductor manufacturing, IEEE Transactions on Semiconductor Manufacturing, vol. 26, no. 4, 578-591, 2013.    W. M. Zuberek, “Timed Petri nets in modeling and analysis of cluster tools,” IEEE Transactions on Robotics Automation, vol. 17, no. 5, pp. 562-575, October 2001.
Since two decades ago, cluster tools have been increasingly adopted in wafer fabrication for high quality and low lead time. In general, a cluster tool integrates several process modules (PMs), a wafer handle robot (R), and one or more loadlocks (LL) for wafer cassette loading/unloading. In operating a cluster tool, a raw wafer in a loadlock is transported to PMs one by one in a specific sequence, and finally returns to the loadlock where it comes from. The robot executes loading, transportation, and unloading operations. It can be a single or dual-arm one, thus resulting in a single or dual-arm cluster tool. A multi-cluster tool is composed of multiple single-cluster tools, as shown in FIG. 1, which are interconnected via buffers with finite capacity for holding incoming and outgoing wafers.
Extensive studies have been done in modeling, analysis, scheduling, and performance evaluation for single-cluster tools [Perkinson et al., 1994 and 1996; Venkatesh et al., 1997; Zuberek, 2001; Wu et al., 2011 and 2012; and Wu and Zhou, 2010a, 2012a, and 2012b]. These studies reveal that a cluster tool operates in a steady state for most of time. A cluster tool operates in one of two modes called transport-bound and process-bound regions. When the wafer processing time dominates the operations such that the robot has idle time, it is process-bound, otherwise it is transport-bound if the robot is always busy. Practically, the robot task time is much shorter than wafer processing time and can be assumed to be a constant [Kim et al., 2003]. Thus, in practice, a cluster tool is often process-bound. In a process-bound region, a pull schedule (backward schedule) is optimal for a single-arm cluster tool [Kim et al., 2003; Lee et al. 2004; Lopez and Wood, 2003; and Dawande, 2002], and a swap scheduling is optimal for a dual-arm cluster tool [Venkatesh et al., 1997; and Drobouchevich et al., 2006]. However, these results are applicable only when there is no strict wafer residency time constraint.
Some wafer fabrication processes must meet strict wafer residency time constraints, thus leading to a complex scheduling problem [Kim et al., 2003; and Lee and Park, 2005]. Studies have been done for scheduling dual-arm cluster tools with wafer residency time constraints in [Kim et al., 2003; Lee and Park, 2005; and Rostami et al., 2001], and methods for finding an optimal periodic schedule are presented. To improve computational efficiency, this problem is further studied in [Wu et al., 2008a; and Wu and Zhou, 2010a, 2010b, 2012a, and 2012b] for both single-arm and dual-arm cluster tools. They develop a type of Petri net models by explicitly describing the robot waiting. Based on these models, an optimal cyclic schedule can be found by simply determining when and how long the robot should wait such that closed-form scheduling algorithms are developed to find such a schedule. Thereafter, one calls such a method a robot waiting method.
In order to meet complex manufacturing conditions, multi-cluster tools have been used in industry for more than a decade. Since the interconnection of single-cluster tools results in coupling and dependence of the single-cluster tools, their analysis and scheduling are more complicated than that of a single-cluster tool [Chan et al., 2011a]. Up to now, there are only a few research reports on this issue. Based on priority rules, heuristics for their scheduling are proposed in [Jevtic, 2001, Jevtic and Venkatesh, 2001]. Since it is difficult to evaluate the performance of a heuristic method, Ding et al. [2006] develop an integrated event graph and network models for them. Then, an extended critical path method is presented to find a periodic schedule. By ignoring the robot moving time, a decomposition approach is presented for scheduling them [Yi et al., 2008]. By this approach, they are decomposed into individual tools and the fundamental period (FP) of each single-cluster tool is calculated. Then, the FP for the whole system can be obtained by analyzing the robot operations in accessing the buffer modules (BMs). With constant robot moving time, Chan et al. [2011a and 2011b] subsequently tackle their scheduling problem. They develop a polynomial algorithm to find an optimal multi-wafer cyclic schedule.
Since robot task time is much shorter than wafer processing time in practice, a single-cluster tool is mostly process-bound. Hence, the present invention assumes that the bottleneck single-cluster tool in a multi-cluster tool is process-bound. Such a multi-cluster tool is called a process-dominant one [Zhu et al., 2013]. For a process-dominant one, the FP of its bottleneck single-cluster tool must be the lower bound of cycle time for the entire system. It is well-known that a one-wafer cyclic schedule is easy to understand, implement, and control to guarantee uniform product quality [Dawande et al., 2002; and Drobouchevitch et al., 2006]. Thus, it is highly desirable to have an optimal one-wafer cyclic schedule for a multi-cluster tool.
Aiming at finding an optimal one-wafer cyclic schedule, Zhu et al. [2013] study the scheduling problem of a process-dominant multi-cluster tool with a linear topology by using the robot waiting method. Their multi-cluster tool is composed of single-arm cluster tools and single-capacity BMs. They show that there is always an optimal one-wafer cyclic schedule for such a multi-cluster tool and efficient algorithms are developed to find such a schedule. They also present the conditions under which the lower bound of cycle time can be reached by a one-wafer cyclic schedule. For the same systems, this scheduling problem is further studied in [Yang et al., 2014]. It is shown that a one-wafer cyclic schedule to reach the lower bound of cycle time can be always found if all the BMs have two spaces. These results are very important for scheduling multi-cluster tools.
By the aforementioned studies, it is known that, with one-space BMs, the lower bound of cycle time may not be reached by a one-wafer cyclic schedule, which implies productivity loss. With two-space BMs, the maximal productivity is reached. However, cost must be paid for additional spaces. Thus, an interesting and significant question is how to optimally configure the buffer spaces such that a one-wafer cyclic schedule is found to reach the maximal productivity. This motivates us to conduct this study. As done in [Zhu et al., 2013; and Yang et al., 2014], one studies a single-arm process-dominant multi-cluster tool with linear topology. A Petri net (PN) model is developed to describe the dynamic behavior of the system with one or two spaces in a BM. With this model, based on the robot waiting method, one derives the conditions under which a one-wafer cyclic schedule with the lower bound of cycle time can be found for an individual tool such that this tool can operate as if it is independent. Then, an algorithm is presented to find such a schedule and configure the buffer spaces. This algorithm involves simple calculations for setting the robot waiting time and is computationally efficient. Further, the buffer space configuration is optimal in terms of the number of buffer spaces needed.
There is a need in the art for a method for scheduling single-arm multi-cluster tools with optimal buffer space configuration.